<?php
/**
 * <https://y.st./>
 * Copyright © 2019 Alex Yst <mailto:copyright@y.st>
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <https://www.gnu.org./licenses/>.
**/

$xhtml = array(
	'<{title}>' => 'Filesystems',
	'<{subtitle}>' => 'Written in <span title="Operating Systems 2">CS 3307</span> by <a href="https://y.st./">Alexand(er|ra) Yst</a>, finalised and <a href="https://y.st./en/coursework/CS3307/Filesystems.xhtml">archived</a> on 2019-05-15',
	'<{copyright year}>' => '2019',
	'takedown' => '2017-11-01',
	'<{body}>' => <<<END
<div class="APA_title_page">
	<p>
		Filesystems<br/>
		Alexand(er|ra) Yst<br/>
		<span title="Operating Systems 2">CS 3307</span>
	</p>
</div>
<h2>Hard links and symbolic links</h2>
<p>
	Data on disk isn&apos;t known to the system by the human-readable names.
	To identify various files from the surrounding data, the filesystem uses file metadata called inodes.
	Like with most computer-readable data, the inodes are identified by number (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
	That doesn&apos;t really help us as humans.
	For example, I know that my home directory is named after my user account and that by convention, it exists as a subdirectory of the <code>/home</code> directory.
	That makes it really easy to remember that my home directory is at <code>/home/yst</code>.
	However, my home directory&apos;s inode number is <code>1577331</code>.
	I can&apos;t remember that.
	Presenting numbers to people as identifiers doesn&apos;t really work.
</p>
<h3>Hard links</h3>
<p>
	The main human-readable links to files are hard links.
	Hard links exist in directory meta data, and are used to directly look up the inode they refer to.
	Every inode, and thus every file and every directory, has at least one hard link pointing to it (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
	Each time a hard link is added that points to an inode, a counter in that inode is incremented, while each time a hard link is removed, the counter is decremented.
	When the counter hits zero, the file is removed.
</p>
<p>
	It&apos;s worth noting that hard links can only point to files on the same filesystem, meaning you can&apos;t link to files on other drives, or even other partitions on the same drive (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
</p>
<h3>Symbolic links</h3>
<p>
	Unlike hard links, symbolic links aren&apos;t entries in a directory&apos;s file index.
	Instead, they&apos;re actual files, separate from the files they link to, so they have their own separate inodes (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
	Also unlike hard links, symbolic links don&apos;t reference inode numbers in any way.
	Instead, they reference the file path of the file or directory they link to.
	In Linux, all files and directories are accessible via a single, unified file tree, regardless of what filesystem they&apos;re technically a part of.
	That means that by referencing paths instead of inodes, a symbolic link is able to link to any file on the entire machine.
	However, symbolic links are also able to link to files not present.
	For example, I&apos;ve found that when I move (or delete) a file or directory linked to by a symbolic link, the symbolic link still exists.
	However, the link is &quot;broken&quot;, as it references something that isn&apos;t there, so it can&apos;t be used.
	However, recreating the missing file or directory causes the symbolic link to once again function as intended.
	Our textbook refers to these symbolic links referencing non-existent files and directories as dangling references (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
</p>
<h2>Inodes</h2>
<p>
	The word &quot;inode&quot; is short for &quot;index node&quot;, a historic name used due to an early implementation used in early UNIX (and potentially earlier) systems; an implementation that is no longer relevant.
	This implementation stored inodes in an array, and the inode number was the index into that array needed to look up the rest of the inode&apos;s data (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
</p>
<p>
	Inodes store the metadata associated with the file they represent (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
	Each inode is referred to by a number, called the i-number.
	As mentioned above, the i-number used to be an index into an array, but while this is no longer the case, inodes are still stored sequentially.
	This means that using the i-number (along with inode size and the location of the inode bitmap), you can calculate where the inode is stored on disk so it can be looked up and used to find other metadata about the file it represents (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
	Basically, all the data about the file aside from its actual contents is stored in the inode.
	This includes permission-related information, such as who is allowed to read from, write to, and execute the file, the file&apos;s owner, the size of the file, and the file&apos;s location on disk.
	Linux uses this information for a variety of purposes.
	Permission and ownership information is used to determine what the operating system will allow you to do with the file.
	For example, files owned by one user may be marked as unreadable by other users for privacy.
	System files are usually readable by all users, but cannot be written to except by <code>root</code>.
	Data such as direct or indirect pointers is also present in the inode, and is used to locate the pieces of the file on disk (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
	Some more-modern filesystems such as $a[ext4] store extents in the inodes, which are used for the same purpose, but implemented in a better way than pointers.
</p>
<h2>Reading a file from disk</h2>
<p>
	The first block on a partition is the superblock.
	This block holds vital information avout the filesystem, such as what format it uses and where the inode table is located.
	When the filesystem is mounted, this block is read into memory (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
</p>
<p>
	Before a file can be read, its inode must be read, as the inode tells the computer where the file is located on disk.
	To find the inode, the file path has to be traversed.
	If we&apos;re looking for <code>/foo/bar/foobar.txt</code>, we have to read <code>/foo/bar</code>, a directory listing, to know <code>/foo/bar/foobar.txt</code>&apos;s i-number.
	However, to read <code>/foo/bar</code>, we need to read <code>/foo/bar</code>&apos;s inode to find <code>/foo/bar</code> on disk.
	That means we need <code>/foo/bar</code>&apos;s i-number, which we would get from reading <code>/foo</code>, which means we need to read <code>/foo</code>&apos;s inode.
	We need to know <code>/foo</code>&apos;s i-number.
	This logic of needing to read the parent directory goes all the way down to the root directory, <code>/</code>, which has no parent (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
	So where do we go from there?
	Basically, the computer needs some way to know the root directory&apos;s i-number without performing a lookup using the parent directory.
	Most Linux filesystems assign the i-number of <code>2</code> to the root directory (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012), so the rood directory having an i-number of <code>2</code> can simply be hard-coded into the software implementing such a filesystem.
	So with this in mind, inode 2 can be read to find where the root directory&apos;s data is located, that data can be used to find <code>/foo</code>&apos;s i-number, then <code>/foo</code>&apos;s inode can be read and so on.
	The chain is followed recursively all the way until the full file path is taken into account and the inode of the file we want to access, <code>/foo/bar/foobar.txt</code>, is read into memory.
</p>
<p>
	Once the file&apos;s inode is in memory, a <code>read()</code> request can be issued.
	Usually, the read will occur from offset <code>0</code>, which is the beginning of the file (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012), though a different offset may be used if you don&apos;t intend to read the entire file.
	This will read the first block of the file.
	The inode of the file will also be updated to include this read as the last time the file was accessed (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
	The file descriptor pointing to this file in the open file table of the program reading the file will also be updated, so that the next call to <code>read()</code> will read the second block of the file.
	This process can be continued until the whole file has been read.
	Closing the file removed the file descriptor from the open file table, but doesn&apos;t require any writing to disk (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
</p>
<h2>The Fast File System</h2>
<p>
	The original UNIX filesystem treats the disk as if it were $a[RAM].
	It writes new files to new blocks according to which blocks with the lowest addresses are free.
	This results in major fragmentation, as files get spread out across gaps formed from deleted files (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
</p>
<p>
	The Fast File System instead takes a disk&apos;s geometry into account.
	(It&apos;s worth noting that disks no longer report the necessary information to the operating system necessary for this to be done, so modern filesystems instead have to make best-guess estimations.)
	Cylinders are arranged into cylinder groups, and each cylinder group has it&apos;s own structures, including its own superblock, its own inode table, its own inode bitmap, its own data bitmap, and its own data.
	Everything needed to access a particular file is present within one cylinder group, making disk seeks much faster, as data doesn&apos;t need to be read from distant cylinders (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
</p>
<p>
	It&apos;s worth noting that the superblock on each cylinder group didn&apos;t hold separate data as the superblocks of other cylinder groups.
	This data is needed to mount the filesystem, and isn&apos;t specific to one cylinder group.
	Instead, each cylinder group&apos;s superblock was an exact copy of all the other superblocks.
	This redundancy eliminated the superblock as a single point of failure.
	If the main superblock became corrupted, that data could simply be copied from one of the other superblocks (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
	This made the Fast File System a more reliable filesystem than the original UNIX filesystem.
</p>
<p>
	The data bitmap was used to find adequate free spaces when available, so large files didn&apos;t need to be fragmented nearly as often (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
	Again, this was a major improvement over the original UNIX filesystem, and is something I think Microsoft should learn from and implement in their own filesystems.
	There&apos;s no excuse for fragmentation except when the disk is too full for large free spaces to be found.
</p>
<p>
	The Fast File system attempts to balance directories across cylinder groups.
	More interestingly, it tries to keep non-directory files on the same cylinder as the directory they&apos;re in.
	That means that once a seek has been issued to reach the directory the file is in, the seek needed to reach the inode of that file will be short (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
	And of course, because the inode and the file&apos;s data are also on the same cylinder group as one another, the seek to reach the data after having read the inode will also be short.
	It&apos;s also often the case that files within the same directory will be used together, for example, as assets by some application (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
	In such cases, reading all these files will again be faster because they&apos;re located neat one another on disk, within the same cylinder group.
</p>
<p>
	While most files are kept unfragmented in the Fast File System, it&apos;s worth noting that filling up a cylinder group is undesirable, as it prevents now files within the directories of that cylinder group from being added to the same cylinder group as their directory, adding seek time to those files.
	To avoid this issue, large files are deliberately fragmented and spread out across cylinder groups (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
	This makes accessing large files require more seeking, but makes the filesystem perform better for the much more common case of large quantities of small files.
	To accommodate small files, the Fast File System also alocated subblocks instead of full blocks to files that were less than four kilobytes in size.
	If the file size were later increased to reach that threshold, the data would be copied into a full block and the data in the subblocks discarded (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
	This filesystem also introduced buffered writes, which the original UNIX filesystem didn&apos;t have.
	Another technique it used was staggering blocks instead of making them directly sequential, eliminating the full rotation needed to get back to the next block, as the disk would usually rotate too far under the head after the previous block had been read but before the $a[OS] could issue a read for the next block.
	This method was called parameterization, and worked on older disks because they reported their specifications to the operating system.
	Modern disks no longer do this, so parameterization is no longer possible (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
</p>
<p>
	Another improvement made by the Fast File System was the addition of long file names.
	Previous filesystems used a fixed file name length, such as eight characters.
	This was also the filesystem to introduce symbolic links and the atomic file-renaming function (Arpaci-Dusseau &amp; Arpaci-Dusseau, 2012).
</p>
<h2>Windows versus Linux filesystems</h2>
<p>
	The advantage of Windows filesystems is that they enjoy wide support across operating systems.
	Nearly any modern operating system can read from and write to a Windows filesystem.
	Due to how popular Windows is in the desktop ecosystem, support for Windows-based filesystems is programmed into many other operating systems, such as Linux and OS X.
	Unfortunately, that&apos;s the only real advantage.
	Windows filesystems are prone to fragmenting, while Linux filesystems actively reduce and often even prevent fragmenting.
	Modern versions of Windows perform defragmentation automatically, so the user doesn&apos;t have to initiate the process themself (Hoffman, 2016), but on a Linux filesystem, the fragmentation doesn&apos;t happen in the first place, so it doesn&apos;t need to be defragmented at all.
	Windows filesystems also have terrible file name support, while Linux filesystems support any and all characters in file names, with the exception of the null byte and the slash character (which is reserved as a path separator).
	For example, I keep the files in my music collection named after the tracks they contain.
	I have a song called &quot;Are You Having Fun?&quot;, by Josh Woodward.
	If my mobile&apos;s $a[SD] card were formatted as $a[FAT] or $a[NTFS], a file named &quot;Are You Having Fun?.ogg&quot; would not be allowed to exist.
	Renaming one file would be no big deal, but I have a large music collection, and many song and album names contain various normal punctuation characters that don&apos;t work on Windows filesystems.
	It&apos;d be a huge pain to go through and find the files that needed to be renamed, make copies of them, rename the copies, and transfer the copies to my mobile&apos;s $a[SD] card instead of the properly-named files.
	However, because my $a[SD] card is instead formatted as $a[ext3], the proper file names including punctuation are allowed.
	And because Android and its forks are Linux-based, my mobile is able to read the $a[ext3] filesystem and make use of the better filename character support.
	It really shouldn&apos;t bee too much to ask to be allowed to use basic characters such as question marks in file names, but Windows filesystems simply don&apos;t support it.
</p>
<h2>Conclusion</h2>
<p>
	I&apos;ve known how symbolic links work for a long time, but it was interesting to learn how and why hard links work.
	I&apos;ve heard of inodes and knew they had to do with files, but I wasn&apos;t sure what those were before this week either.
	I now better understand what the error messages my computer spews out at me after being powered back on from having been shut down improperly mean.
	I&apos;ve noticed that after my battery had died due to my not noticing how little power is left and getting my laptop plugged into an outlet, I get a wall of messages about orphaned inodes needing to be removed.
	I now see that these are inodes for files that no longer have a parent directory.
	They were probably temporary files or files that had been partly cached an not written to disk fully yet.
	Either way, the reference count has probably dropped to zero, meaning they have no parent directories, making them orphans.
	As for filesystem support, I&apos;m glad I don&apos;t have to interact with Windows-based operating systems.
	They don&apos;t support decent filesystems, and it&apos;d be a major pain in the butt to have to deal with the filesystems Windows provides compatibility with.
</p>
<div class="APA_references">
	<h2>References:</h2>
	<p>
		Arpaci-Dusseau, A., &amp; Arpaci-Dusseau, R. (2012). <a href="http://pages.cs.wisc.edu/~remzi/OSTEP/file-implementation.pdf">40: File System Implementation</a>. Retrieved from <code>http://pages.cs.wisc.edu/~remzi/OSTEP/file-implementation.pdf</code>
	</p>
	<p>
		Arpaci-Dusseau, A., &amp; Arpaci-Dusseau, R. (2012). <a href="http://pages.cs.wisc.edu/~remzi/OSTEP/file-ffs.pdf">41: Locality and The Fast File System</a>. Retrieved from <code>http://pages.cs.wisc.edu/~remzi/OSTEP/file-ffs.pdf</code>
	</p>
	<p>
		Arpaci-Dusseau, A., &amp; Arpaci-Dusseau, R. (2012). <a href="http://pages.cs.wisc.edu/~remzi/OSTEP/file-intro.pdf">39: Interlude: Files and Directories</a>. Retrieved from <code>http://pages.cs.wisc.edu/~remzi/OSTEP/file-intro.pdf</code>
	</p>
	<p>
		Hoffman, C. (2016, September 28). <a href="https://www.howtogeek.com/115229/htg-explains-why-linux-doesnt-need-defragmenting/">Why Linux Doesn&apos;t Need Defragmenting</a>. Retrieved from <code>https://www.howtogeek.com/115229/htg-explains-why-linux-doesnt-need-defragmenting/</code>
	</p>
</div>
END
);
